To solve the synchronization problem of audio and video, an improved algorithm of audio-video synchronization coding based on H.264 inter-frame prediction was proposed. The algorithm introduced the concept of variable code length. The audio encoding data was divided into several code groups, and each code group had 2 or 3 bits of embedded data. In the stage of H.264 inter-frame prediction, the mappings between various variable size blocks and the data of code groups were based on formula. The coding method was dynamically determined for the macro block modes coding according to embedded data, and a proposed decoding method could extract the corresponding data according to the mapping relationship. Finally, the 4×4 macro block mode was used to indicate the end of the audio data.The experimental results show that the proposed algorithm enables the Peak Signal-to-Noise Ratio (PSNR) of video samples to reduce by 0.031dB, the bit rate to increase by 5.16% and the overhead to increase by 1.97%, but the embedded audio data can be correctly and completely extracted. Therefore,the algorithm can implement the synchronization of audio and video coding while increasing the data embedding capacity, maintaining the quality of video, ensuring the correctness and completeness of the data.